package dp;

import org.junit.Test;

import java.util.Arrays;

public class LongestPalindrome5 {

    @Test
    public void test() {
        longestPalindrome("babad");
        longestPalindrome("cbbd");
        longestPalindrome("a");
        longestPalindrome("ac");
        longestPalindrome("bb");
    }

    // redo at 2022.02.27
    public String longestPalindrome(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];

        // 初始化二维数组, 同时提前处理k=1的情况
        for (int i = 0; i < s.length(); i++) {
            Arrays.fill(dp[i], false);
            dp[i][i] = true;
        }

        int start = 0;
        int len = 1;
        // 这里k从2开始
        for (int k = 2; k <= s.length(); k++) {
            for (int i = 0; i <= s.length() - k; i++) {
                int j = i + k - 1;
                dp[i][j] = (s.charAt(i) == s.charAt(j));
                if (k > 2) {
                    dp[i][j] = dp[i][j] && dp[i+1][j-1];
                }
                if (dp[i][j] && k > len) {
                    start = i;
                    len = k;
                }
            }
        }
        return s.substring(start, start + len);
    }

    // passed before
    public String longestPalindrome0(String s) {
        int maxLen = 1;
        int startIndex = 0;

        boolean[][] dp = new boolean[s.length()][s.length()];

        // 注意: k表示长度, 所以上限是字符串长度: 1<k<=s.length.
        for (int k = 1; k <= s.length(); k++) {
            // 注意: 由于内层下标时 i+k-1, 所以i的上限要特别注意是 0<=i<=s.length-k.
            for (int i = 0; i <= s.length() - k; i++) {
                // 注意: 对于k=1和2的场景, 要放到内层循环里统一处理, 不要放外面. 否则会遗漏maxLen的更新.
                if (s.charAt(i) == s.charAt(i + k - 1) && (k <= 2 || dp[i + 1][i + k - 2])) {
                    dp[i][i + k - 1] = true;
                    if (k > maxLen) {
                        maxLen = k;
                        startIndex = i;
                    }
                } else {
                    dp[i][i + k - 1] = false;
                }
            }
        }
        String sub = s.substring(startIndex, startIndex + maxLen);
        System.out.format("s: %s, maxLen: %s, palindrome: %s\n", s, maxLen, sub);
        return sub;
    }
}
